#include<bits/stdc++.h>
#define int long long
#define N 3000006
using namespace std;

int c, T;
int n, k;
int a[N], b[N], z[N]; //z[i]表示每户的小朋友数
int f[2510][2510], g[2510][2510]; 
void Sol() {
    cin >> n >> k;
    int w = 0;
    for(int i = 1; i <= n - 1; i++) cin >> a[i], w = max(w, a[i]);
    a[0] = w;
    for(int i = 1; i <= k; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) z[i] = 0;
    for(int i = 1; i + k - 1 <= n; i++)
    for(int j = i; j <= i + k - 1; j++) z[j] += b[j - i + 1];
    for(int i = 0; i <= n; i++)
    for(int j = 0; j <= w; j++) f[i][j] = 0, g[i][j];
    for(int i = 1; i <= n; i++) 
    for(int j = 0; j <= w; j++) {
        if(j <= a[i - 1]) f[i][j] = max(g[i - 1][a[i - 1] - j] + j * z[i], f[i][j]);
        g[i][j] = max(j >= 1 ? g[i][j - 1] : 0, f[i][j]);
    }
    cout << g[n][w] << endl;
}
signed main() {
    freopen("festival.in", "r", stdin);
    freopen("festival.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> c >> T;
    while(T--) Sol();

    return 0;
}